package org.example;
import java.io.*;
import java.util.ArrayList;

class Bounds {
    final Integer x;
    final Integer y;
    final Integer size;
    Bounds(Integer x, Integer y, Integer size) {
        this.x = x;
        this.y = y;
        this.size = size;
    }

    Boolean intersects(Bounds other) {
        return !(x > other.x + other.size ||
                x + size < other.x ||
                y > other.y + other.size ||
                y + size < other.y);
    }

    /**
     * 区域是否包含点，注意计算时按半开区间计算点是否在范围内。
     * 即给定一个点(x0,y0)，如果x0 ∈ [x, x+size),y0 ∈ [y, y+size)即判定它在范围内。
     */
    boolean contains(Point pt) {
        return pt.x >= this.x && pt.x < this.x + this.size && pt.y >= this.y && pt.y < this.y + this.size;
    }
}

class Point {
    final Integer x;
    final Integer y;
    Point(Integer x, Integer y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

interface QuadTree extends Serializable {
    Bounds getBound();
}

class Leaf implements QuadTree {
    public ArrayList<Leaf> neighbors;
    public Bounds bound;
    public Boolean isObstacle;

    public Leaf(Bounds bound, Boolean isObstacle) {
        this.neighbors = new ArrayList<Leaf>();
        this.bound = bound;
        this.isObstacle = isObstacle;
    }

    public Bounds getBound() {
        return this.bound;
    }

    public Point center() {
        Integer centerX = this.bound.x + this.bound.size/2;
        Integer centerY = this.bound.y + this.bound.size/2;
        return new Point(centerX, centerY);
    }

    public void findNeighbors(QuadTree t) {
        if (t.getClass() == TreeNode.class) {
            TreeNode node = (TreeNode)t;
            if (!this.bound.intersects(node.bound)){
                return;
            }
            findNeighbors(node.nw);
            findNeighbors(node.ne);
            findNeighbors(node.sw);
            findNeighbors(node.se);
        }
        else if (t.getClass() == Leaf.class) {
            Leaf l = (Leaf) t;
            if (!l.isObstacle && l != this && this.bound.intersects(l.bound))
                this.neighbors.add(l);
        }
    }
}

class TreeNode implements QuadTree {
    public QuadTree nw;
    public QuadTree ne;
    public QuadTree sw;
    public QuadTree se;
    public Bounds bound;

    TreeNode(QuadTree nw, QuadTree ne, QuadTree sw, QuadTree se, Bounds bound) {
        this.nw = nw;
        this.ne = ne;
        this.sw = sw;
        this.se = se;
        this.bound = bound;
    }

    public Bounds getBound() {
        return this.bound;
    }
}